package graph;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * description:
 * author:张腾
 * date:2021-04-11
 */

/**
 * 深度优先搜素
 * 当一个节点有兄弟节点和子节点时，优先搜索子节点
 */
public class DepthFirstSearch {

    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点和s顶点相通
    private int count;

    //构造深度优先搜索对象，使用深搜找出G图中s顶点的所有相通顶点
    public DepthFirstSearch(Graph G,int s){

        this.marked = new boolean[G.V()];
        this.count = 0;

        dfs(G,s);
    }

    //使用深搜找出G图中v顶点的所有相通顶点
    private void dfs(Graph G,int v){

        //将v顶点标识为已搜索
        marked[v] = true;

        for (Integer w : G.adj(v)){

            if (!marked[w]){
                dfs(G,w);
            }
        }
        count++;
    }

    //判断w顶点和s顶点是否相通
    public boolean marked(int w){

        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count(){

        return count;
    }
}
